package com.dynamic;

import java.util.Arrays;

public class Dynamic {
    public static void main(String[] args) {
        int t = 7;
        long frog = Dynamic.frog(t);
        System.out.println(frog);
    }

    /**
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * @param n
     * @return
     */
    public static long frog(int n) {
        // f[n]表示到n层的跳法数量，到n层有两种跳法 一种从n-1层跳上来另一种从n-2层跳上来，因为青蛙能跳一或二级。
        //f[n] = f[n-1] + f[n-2]
        // 找到初始值 f[0]=0 f[1] = 1 f[2] = 2 ; f[3]=f[2] + f[1] = 3;
        long[] dp = new long[3];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            // dp[i] = dp[i-2]+dp[i-1]; 空间复杂度高
            dp[2] = dp[2] + dp[1];// 辗转相加 降低空间复杂度
            dp[1] = dp[2] - dp[1];
        }
        System.out.println(Arrays.toString(dp));
        return dp[2];
    }
}
